HPAVC

home *** CD-ROM | disk | FTP | other *** search

/ HPAVC / HPAVC CD-ROM.iso / pc / CIS_GAME.ARJ / QCOLL1.THD < prev next >

Wrap

Text File | 1993-07-01 | 38.2 KB | 832 lines

_________________________ Subj: Collision Detection _________________________ Fm: Mark Betz/GD SL 76605,2346 # 172652 To: David J. Leach Jr 70511,1573 Date: 29-May-92 17:50:56 ... There are two methods I'm familiar with for collision detection. One is simply based on range checking. That is, if a ball is 10 x 10 pixels, and a wall is at y = 50, then if the ball's position is at y = 41 you have hit the wall. Another method that was described here recently is interesting. In this method specific colors are reserved for parts of the game, and you test for a collision by testing the color value of pixels you are overwriting. --Mark ........................................................................... Fm: Tim Triemstra 70007,6361 # 172779 To: Mark Betz/GD SL 76605,2346 (X) Date: 29-May-92 23:27:10 One final way is for all you people that work in a vector world. The array method is of course the best (if you KNOW you're touching something, it's easy to react) However, in games like Wolfenstein 3D and Ultima Underworld you are dealing with HUGE worlds, and an unlimitted number of locations. In these cases you'd have to use right-triangle trig to determine the outcome of a sentence like: "In 3 seconds the character will move approximately 3 units from the current position. At this angle the hypotoose (sp?) would be 3 units. Use this distance to determine the offset in the Y and X planes. Run the same check on the wall <ie: wall distance and angle>. Do a check to see if the two points at the end of the calculation are in the same space." This is much more complex, but if you develop a game with an unlimitted number of locations it would be great to develop a set of routines for maintaining objects within a world like this. This method is by FAR the most adjustable. Hopefully this didn't confuse you too much, but it could't hurt to ask a question or two now that I've made it alot more complex. I'm always willing to dig out my calc book. Tim T. ........................................................................... Fm: yngvi 76703,3046 # 173700 To: Tim Triemstra 70007,6361 (X) Date: 01-Jun-92 14:13:06 I used a similar method for collision detection in one of my early games -hwoever, you can skip some of the calculations by defining an approximation: briefly, consider a point A, approaching a line B-C. this forms a triangle, with the B-C as the base. as the point comes closer, the combined length of the two lines from the point begin to approach the value of the line itself: A-B + A-C --> B-C you can do rough calcs of the line lengths, and dont need to use the pythagorean equation (with square roots). This was published as an article in Computer Language about 5 or so years ago. Another trick is to do some rough calcs first to see if the two objects are even worth investigating. There are also some point, polygon intersection algorithms that can be used for more precise details. ........................................................................... Fm: Stuart Patterson 76507,1602 # 188687 To: All Date: 17-Jul-92 11:09:04 Well here I go again. I've been trying to figure the best method for Collision Detection. One method I come up with is to use the lower 128 colors to represent background and none destructive objects then use the upper 128 to represent objects which can be collided with. This method seems ok in 256 color mode (13h). Does anyone have any thoughts on better methods? I know you guys don't use this method in 16 color mode! thanks, stuart patterson ........................................................................... Fm: Mark Betz/GD SL 76605,2346 # 188802 To: Stuart Patterson 76507,1602 (X) Date: 17-Jul-92 18:24:40 Hi, Stuart. I think Dan has used that color-based detection method. Most of the simpler animations I've seen have used range-checking, which means dpo compares against the other objects in the vicinity. I've used this technique myself, and it can be pretty fast. Usually most of the surfaces and objects in a frame can be rejected by trivial tests (the wall is on the other side of the room, etc). When you get down to the few objects you might be colliding with you check for coordinate overlap. --Mark ........................................................................... Fm: Dan R Corritore 70243,1110 # 189539 To: Mark Betz/GD SL 76605,2346 (X) Date: 19-Jul-92 23:05:22 <<I think Dan has used that color-based detection method.>> NOT!!! It was Rasch, Rasch, Rasch!!! Don't give me the credit! I use the method of floor-maps, and events. The floor maps are just bit masks which have bits set where there is an object. The latter, events is everything that is not a stationary object, OR/AND any area in which some activity will occur when the current sprite enters the bounds.(Say, walking into the range of a motion detector..which could trigger doors to open,bells to alarm, fat lady's to sing, etc.). _Dan ........................................................................... Fm: Mark 'SAM' Baker 100025,444 # 189767 To: Stuart Patterson 76507,1602 (X) Date: 20-Jul-92 17:18:41 Using the first 128 colours can work; but I find it's better to use the colours for 'planing' the screen; breaking down into blocks of 64 colours/plane: and to use co-ordinates for collision detection (though this means using 3-d coordinates. Mark ........................................................................... Fm: Dan R Corritore 70243,1110 # 189886 To: Mark 'SAM' Baker 100025,444 Date: 20-Jul-92 22:40:44 <<and to use co-ordinates for collision detection (though this means using 3-d coordinates.>> Using coordinates for collision detection hardly requires you to use 3-d coordinates, unless you are doing some specific 3-d game.. My game system has a 'sorta kinda 3-d system', but its collision detection is just with X-Y-coordinates. So far,this means that even if a sprite is jumping way up in the air, it will still be detected by someone on the ground. I've done a little compensating for that, though (well, there just HAS to be birds in the game), but, for the most part, its 2-d. A good example of a coordinate-non-3d collision detection method is of racing cars viewed from a birds-eye-perspective. The cars image and its spot on the ground are both the same, so if the image crashes into something, so does the car. But if the cars going diagonally, the collision detection would have to go a little further to ensure an 'exact' hit,because of the space on the sides--in which color detection could work. _Dan ........................................................................... Fm: Dan R Corritore 70243,1110 # 190751 To: Mark 'SAM' Baker 100025,444 (X) Date: 23-Jul-92 00:55:27 I am doing the same type of work you are, although slightly different. I have the possibility of each sprite being behind 14 different masks, and the masks are not done with special colors. The masks are separate from the image, therefore giving more flexibility and no restrictions. The way I have the masks is that each bit represents one pixel on the screen(but for the current mask). I was thinking of changing this to a more flexible implementation, but it would slow down the animation, and I want to keep my speed.This more flexible implementation(which doesn't increase the size of memory needed to store it) allows 256 total masks to be implemented. But, for now, 14 masks seems good enough to me. For my system,if a sprite is behind a bush and another is in front of it, and they are headed straight for each other, collision won't be an issue, since the bush is defined in the floor mask as a permanent object, and the sprites would stop moving once they hit the bush. I could also define the bush as a temporary object, and the other sprites would just bang into the bush-that being their collided object. _Dan ........................................................................... Fm: Dan Corritore 70243,1110 # 266746 To: KGliner 70363,3672 Date: 23-Dec-92 13:59:48 This is in response to a message you posted to me a while ago. I was just looking through some old messages and deleting them, when I came across yours(again). I've been thinking about it, and have decided not to use what you said..(which I wasn't going to anyway).. You said to have the sprites connected to the tiles in a tile-based-world for faster collision detection. This would require about 4 bytes per tile (or, if used efficiently, 2 bytes)..which would be tacked on right after the tile index (of course). Anyway, it's possible that this scheme will fail, and Murphy's Law states that if it can fail, it will! <G> Anyway, saying you have a sprite that spreads across 2 or more tiles.. you stated that you would only require one tile to point to the sprite..this isn't smart at all, since when checking for collision detection it is definitely possible to miss a sprite like this (especially if, say, the sprite was spread across 4 tiles). Connecting every tile that it covers to it (by pointing them all to the sprite) corrects this problem, but it imposes another problem. If you have more than one sprite on a tile, you would need to have a linked list, and when a sprite has 2 or more tiles connected to it, it's impossible for the sprite to know how many pointers it should have to next sprites. Unless, of course, you create an array of pointers (with a pointer to that array, and a number indicating how many pointers you have).. well, anyway, you get the picture..it would be too complicated to keep it failsafe..even if it is a very unlikely thing to happen. So, what's your take on this? _Dan ........................................................................... Fm: Dan Corritore 70243,1110 # 270060 To: KGliner 70363,3672 (X) Date: 30-Dec-92 00:08:40 <Slapping self in head> Duh, I should have thought of that!<G> It won't be that much harder to check a few extra tiles around the collision area, but it might make it a wee bit slower.. Ok, say if your tiles were 16*16, and your biggest sprite was 20*20, this would require, using the worst case scenario, checking 3 x * 3 y = 9 tiles, being that the tile pointer to the sprite could start in that big area. Diagram below: (backslashes is the area taken up by the sprite) | | | | | \\\\\\20x\\\\\\\ | | \ | | \ | |---16x--\-|----------|-\--------| | \ | | \ | | \ | | 20 | 16 \ | Inside | y | y \ | | \ | | \ | | \ | |--------\-|----------|-\--------| | \ | | \ | | \\\\\\\\\\\\\\\\ | Hopefully that came out right. If not, it was a 3*3 box of 16*16 tiles with a 20*20 figure in the middle of them all..a possible situation. So, tell me now, is it still worth all that extra memory to use this collision detection scheme? Have you tested this out already? Thanks, _Dan ........................................................................... Fm: KGliner 70363,3672 # 270127 To: Dan Corritore 70243,1110 (X) Date: 30-Dec-92 03:54:55 Well, if you only have to do 9 collision checks per moving object (and simple checks too as they involve only seeing if a ptr is nil), and you have 100 moving objects, then that's 900 checks per cycle. Much better than comparing 100 objects to 99 others for 9900 checks per cycle (and those would be far more complicated than just seeing if a ptr is nil). Now, in the example you give, I'd say you'd need four pointers for the sprite because it is larger than your tile size in both dimensions by more than 1x but less than 2x. This isn't going to be terribly efficient if you've got a lot of 20x20 sprites and want to work with 16x16 tiles. Better to just make your tiles 20x20. As for how practical this is depends a lot on the specifics of what you want to do. If your largest sprite is only 40x40, then make all your tiles 40x40 too, and you never have to have more than one ptr to a sprite (although you still need to be able to have more than one ptr from a tile to multiple sprites on the tile). The larger the tiles, the less memory you use, but the more sprites that might actually be on that tile (having no effect on this stage of collision detection but slowing down the next stage when you do more complicated checks). How efficient this is depends on how many sprites you typically have moving at once, how crowded the sprites are likely to get, and just how big the sprites actually are. I haven't tried to implement any of this, and unfortunately I probably won't since I don't think any of the designs I want to do would require such a scheme (hey, I'm just making this up as I go). I have used tiles w/ptrs to sprites before, but only in a strategy game where the sprites couldn't overlap the tiles. Hope that answers your question... Kevin ........................................................................... Fm: Dan Corritore 70243,1110 # 270424 To: KGliner 70363,3672 (X) Date: 30-Dec-92 16:13:17 << As for how practical this is depends a lot on the specifics of what you want to do. If your largest sprite is only 40x40, then make all your tiles 40x40 too, and you never have to have more than one ptr to a sprite..>> Even with sprites the same size as the tiles, you have the possibility of it overlapping 4 different tiles at a time. Sure it's less, but it's still the same tough spot. I think I'll try both ideas to see which one works faster/better. If you don't remember what the other idea was, it was checking for collision using a tree, and the tree would be divided up into equal sections.. what I mean, is that if your tile world is 32000 pixels wide by 32000 pixels high, the first tree node would be at 16000,16000, then from 16000,16000 go half again, etc.. until you reach a good enough number. Thanks again, _Dan ........................................................................... Fm: KGliner 70363,3672 # 270579 To: Dan Corritore 70243,1110 (X) Date: 30-Dec-92 20:54:19 Dan- I'm not sure I understand the problem that arises from having a sprite overlap 4 tiles. As long as only one of the tiles points to the sprite, and this tile is the one most overlapped by the sprite, and you check the surrounding 8 tiles when doing collision checks, then it's impossible for a collision to be missed. And it still only costs you a maximum of 9 checks per object that actually moves. Kevin ........................................................................... Fm: Dan Corritore 70243,1110 # 270740 To: KGliner 70363,3672 (X) Date: 31-Dec-92 00:09:10 << I'm not sure I understand the problem that arises from having a sprite overlap 4 tiles.>> Well, for one, it adds a level of complexity! I know, it shouldn't make a difference to a 'real' programmer, but right now, I'm going to go with the simpler tree method I said.. if it's too slow I'll consider your approach, but only if I have the memory to spare(and want to take the time to do the extra tile collision checks). Thanks for the idea, though.. _Dan ........................................................................... Fm: Mark Hula 100047,110 # 318482 To: All Date: 22-Mar-93 14:40:08 Hi All, I'm scrolling a large map 2 pixels in any direction and I want to perform collision detection against the scenery.The main character is always in the centre (doesn't physically move).I guess I could store all the x+y's of all 'solid' scenery (all scenery is square as such) and simply see if the main characters "square box" has gone into one of the scenery but this seems tacky and inefficent,does anyone know of a better solution???? Not colour checking!-thats even tackier! Thanks MC ........................................................................... Fm: Dan Corritore 70243,1110 # 318540 To: Mark Hula 100047,110 (X) Date: 22-Mar-93 16:24:14 I'm not sure what you mean by 'tacky'.. that's a good enough solution for you to use, but if you mean it's not fast enough (if there's too many things to check against), than I'll give you a solution someone else gave me! (I won't give you any names, but his intials are Kevin Gliner!<g>) Actually, he gave me a different solution, but it's pretty close to what he suggested. Just divide the landscape into sections, preferably having the sections be the size of the largest object you'll use, and then have the objects 'connected' to the section they are in. For doing collision detection this way, you'd need to only check a few sections instead of the whole map. In some cases, this might take up too much space.. so you should judge for yourself whether or not this is the best approach. Another approach is to have all the objects connected in a tree, but that's a bit more complicated, since you must keep the x1,y1-x2,y2 locations for the objects. And finally, another last approach would be to have the landscape tiled, so that you can have tiles with optional 'walk/no-walk' areas. _Dan ........................................................................... Fm: Danator 71601,3551 # 336877 To: Game Programers Date: 18-Apr-93 17:44:19 Hello all, I have a quistion about detecting colissions in arcade games and in 3D applications. I've allmost driven myself crazy trying to figure this out and I havent been able to find any kind of reference material that deals with it. This is suprizing because collision detection plays a very important role in games. I used to have a AMIGA computor and a simple language called AMOS that had routines that handled collisions. That was nice but now I have a PC and am using C. I also use Fastgraph but, it doesn't have routines for detecting collisions. Anyway, I felt that this was probably the best place to come to find out. I am sure that there are several others who would like to know how it's done, so I think it would be a good thread for disscusion. If you've got some neat tricks or even not so neat tricks, let the rest of us poor souls in on them. Thanks a million, Dan Weatherman 71601,3551 ........................................................................... Fm: John Dlugosz [ViewPoint] 70007,4657 # 337148 To: Danator 71601,3551 (X) Date: 18-Apr-93 21:29:01 Can you be more specific? Colliding with walls is easy. Colliding with other objects is also easy, but there are ways to make it faster. --John ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 337469 To: John Dlugosz [ViewPoint] 70007,4657 (X) Date: 19-Apr-93 13:00:12 I'm interested in this topic. For rudimentary collision detection I would probably think to compare bounding rectangles, but for some sprites this would result in some unrealistic collisions. I've thought about using masks with a 1 bit for each non-transparent pixel in the sprites, and then ANDing the intersection together to see if anything came out set. I'm not sure this would be fast enough, though. At least one person here was using a color-based scheme at one point, where specific colors were reserved to specific sprites and objects. I think he abandoned it eventually. --Mark ........................................................................... Fm: Dan Corritore 70243,1110 # 337479 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 19-Apr-93 13:42:04 You're speaking of Rasch, yes? I remember him mentioning that he reserved specific colors for sprites and objects, and would do collision detection based on what colors hit others, or somesuch. I believe he said he did it because he did some sort of complex rotation on the sprites, making it hard to figure out their masks/positions. It was a neat idea, to say the least! Anyway, you say he abandoned the idea? Thanks, _Dan ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 337863 To: Mark Betz/Ass't SysOp 76605,2346 (X) Date: 19-Apr-93 22:53:33 Hi Mark - I use the intersection of the bounding rectangle first to determine if it's necessary to and the masks together. What I found that was usually, if the rectangles intersected you found a 1 in the ANDed mask fairly quicky. Worst case was if the was no intersection, and then you ended up searching the entire ANDed mask. That happened with odd shaped objects, say like a ring. It still worked out pretty well, even in Windows <g>. Bob ........................................................................... Fm: Mark Betz/Ass't SysOp 76605,2346 # 337922 To: Bob Provencher/GD SL 71621,2632 Date: 20-Apr-93 00:41:18 That makes sense, Bob. Always perform the simple test for trivial rejection first, and the drop through to the more specific comparisons on the result set. See, you can learn how to program games while doing database design <g>. --Mark ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 337220 To: Danator 71601,3551 (X) Date: 18-Apr-93 23:24:08 Hi Danator, Welcome to GAMERS! What I usually do is first test that the bounding rectangles of the two objects intersect, then check that the masks of the two objects overlap. Others will probably jump in with more, if you need more specifics, just ask. Bob ........................................................................... Fm: Teut Weidemann 100022,2466 # 337290 To: Bob Provencher/GD SL 71621,2632 (X) Date: 19-Apr-93 02:04:10 For fast action games (50-60 frames/sec) checking with the collision mask is too time consuming. Checking with a frame that is smaller than the object itself fills the need. The most importand "rectangle" is that of your character in the game (ie. MArio or Sonic). In our games it helped a lot to sort all objects along their YX coordinates (which was one word). So we tested all objects top to down only that far: Y+YSize. this saved a lot of time. Actually sorting all objects helped with 8 directional scrolling, too. But thats another story. Teut ........................................................................... Fm: Jaimi the OverTaxed 71700,1202 # 337696 To: Danator 71601,3551 (X) Date: 19-Apr-93 19:59:37 Dan, Here's a simple algorithm to check if two boxes intersect. It's part of a box class that I wrote, but it's pretty much self explanatory. Its main advantage being its very fast. I just shopped this out of some code so you'll have to tidy it up. this actually calculates a box that is the union of two boxes. if the boxes intersect, the width (w) will be positive. void BOX::Union(BOX &bx1,BOX &bx2) { x=MAX(bx1.x,bx2.x); y=MAX(bx1.y,bx2.y); w = MIN(bx1.x2,bx2.x2)-x; h = MIN(bx1.y2,bx2.y2)-y; if ( w > 0 && h > 0 ) SetBox(x,y,w,h); else SetBox(0,0,0,0); } P.S. It looks all formatted correctly from here, but you know how these message editors are. by the time CIS reformats it may look like junk. ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 337865 To: Danator 71601,3551 Date: 19-Apr-93 22:53:44 Hi Danator - Here's how I normally detect intersection between two rectangles. In C++, assuming we have a Rect class: Assume you've defined a min and max, and that 0, 0 is the lower left corner of the screen: int Rect::isIntersect( Rect r ) { return max( left, r.left ) <= min( right, r.right ) && max( bottom, r.bottom ) <= min( top, r.top ); } If you'd like the intersecting rectangle: Assume a constructor: Rect( int left, int top, int right, int bottom ); Rect Rect::Intersect( Rect r ) { if ( isIntersect( r ) ) return Rect( max( left, r.left ), min( top, r.top ), min( right, r.right ), max( bottom, r.bottom ) ); else return Rect( 0, 0, 0, 0 ); } For the union: Rect Rect::union( Rect r ) { return Rect( min( left, r.left ), max( top, r.top ), max( right, r.right ), min( bottom, r.bottom ) ); } ANDing the masks together is another story, and can depend a little on the libs you're using. Hope this helps! Bob ........................................................................... Fm: John Dlugosz [ViewPoint] 70007,4657 # 337782 To: Jaimi the OverTaxed 71700,1202 (X) Date: 19-Apr-93 21:22:13 Mine is a little more efficient. It does not calculate the union if the boxes _don't_ intersect, but leaves the result in an undefined state. In fact, it does the whole thing in one statement! --John ........................................................................... Fm: Jaimi the OverTaxed 71700,1202 # 337869 To: John Dlugosz [ViewPoint] 70007,4657 (X) Date: 19-Apr-93 23:07:01 Yes, john. But leaving a box in an undefined state can lead to errors! Jaimi ........................................................................... Fm: John Dlugosz [ViewPoint] 70007,4657 # 337781 To: Danator 71601,3551 Date: 19-Apr-93 21:22:06 How about: if (intersection (r1,r2, result)) { ... bool intersection (twocorner *a, twocorner *b, twocorner *result) /* finds the intersection of 2 boxes and returns TRUE if intersection exists. */ { return ( (result->ul.x= (a->ul.x > b->ul.x) ? a->ul.x : b->ul.x /* left */) <= (result->lr.x= (a->lr.x < b->lr.x) ? a->lr.x : b->lr.x /* right */) && (result->ul.y= (a->ul.y > b->ul.y) ? a->ul.y : b->ul.y /* top */) <= (result->lr.y= (a->lr.y < b->lr.y) ? a->lr.y : b->lr.y /* bottom */)); } - or - bool window_core::intersection ( const twocorner& a,const twocorner& b,twocorner* result) // finds the intersection of 2 boxes and returns // TRUE if intersection exists. { return ( (result->ul.x= (a.ul.x > b.ul.x) ? a.ul.x : b.ul.x /* left */) <= (result->lr.x= (a.lr.x < b.lr.x) ? a.lr.x : b.lr.x /* right */) && (result->ul.y= (a.ul.y > b.ul.y) ? a.ul.y : b.ul.y /* top */) <= (result->lr.y= (a.lr.y < b.lr.y) ? a.lr.y : b.lr.y /* bottom */)); } ........................................................................... Fm: Teut Weidemann 100022,2466 # 337976 To: Danator 71601,3551 Date: 20-Apr-93 01:40:17 Hmmm, this depends on how you organize your OBJ. Lets say you have two linked lists. One for used (on screen) objecs, one for the empty slots for objects to be displayed. If you sort them by Y (then X) you can start with the first object and look through the list and check their bounding rectangles till the next objects Y is farer then your Y plus your Y-Size. Then go to the next OBJ. This is ONLY neccessary if you have to check every OBJ with every objects. But thats seldom the case. If you have only some objects to check (your player plus bullets) you have to mark them or keep them separate to minimize CPU time. Teut ........................................................................... Fm: Teut Weidemann 100022,2466 # 337979 To: Bob Provencher/GD SL 71621,2632 Date: 20-Apr-93 01:45:37 Yes, I mean the smallest rectangle inside an object (most sprites are 16x16 or 32x32 anyway). The only drawback can be seen as an enhacement of gameplay: If two objects intersect but the rectangles dont, the play got just lucky enough to prevent a collsion. You see that in most coin up games when you nearly miss an object. Masking is ONLY done in fast action games if it depends on gameplay, but I know only a few games who do this. In Turrican (for Amiga, SNES, Megadrive) they use this technology along with sorting all objects along their YX axis. This is only neccessary if you need to check coll. between ALL objects, which is seldom the case. If you need to check your player and your bullets, you have to keep them separate of mark them accordingly. Note: Our actio games are all 100% assembler. Our techies always try to do everything in 50/50 frames a sec. Teut ........................................................................... Fm: Teut Weidemann 100022,2466 # 338684 To: Bob Provencher/GD SL 71621,2632 (X) Date: 21-Apr-93 01:17:24 I meant the smallest bounding rectangle inside an object, but that can vary. We try to resize the rectangle accorningly to the objects looks an purpose, ie. if it is a shot, the rectangle can be pretty small. I worked the the largest publisher in germany (Softgold/Rainbow Arts) as the development director (is that the american name for that job?) and we had some good action titles. Now I am in the games buisiness for advertising, ie. we are developing games for advertising cutsomers like SONY, BLAUPUNKT, germany government, Kraft and more. In germany the deleoper "circle" is still pretty small and only a few got to match the world standard. Teut ........................................................................... Fm: Mark Hula 100047,110 # 338205 To: All Date: 20-Apr-93 13:39:51 Hi All! I'm trying to work out this problem and its really confusing my brain - though I expect its all easy to you lot! :-) The problem is difficult to explain but I'll try: Imagine a 10*10 square,in this square certain blocks are set at random, for example the top left of the square may be: 0 1 2 3 4 5 -------------- 0! ! !*!*!*! ! 1! ! !*!*! ! ! An * indicates a block 'set' 2! ! ! ! ! !*! What I'm looking for is a routine (algorithm no code will do) to search this whole 10*10 map and produce the most optimized groupings into squares/rectangles of blocks as possible (confused!) Take the *** pattern, this can be a *** followed by a ** or a ** and a *. ** ** I know its not clear!,in that above example of course either choice would do as the "shape" can only be divided into 2 "square" possiblities.But the shape ** optimally could be a ** and a *.i.e. don't want 3 ** and a *.!!!!! ** ** ** ** * Clear as mud!-I know!!,if your wondering what the heck this is all for well!, its for a collision routine!.Findings "squares" isn't too tricky ,finding optimal ones is-it makes my head hurt! Any help much welcome!! MC ........................................................................... Fm: Mark Hula 100047,110 # 338891 To: Mark Hula 100047,110 Date: 21-Apr-93 13:05:46 !-yep the picture is wrong! 012345 0 ** 1 *** 2 * i.e. blocks could be ** and *** and *,but whats the optimal way to find them (the least number)-the above could also be a ** ** and 2 *. ........................................................................... Fm: Mark Hula 100047,110 # 345381 To: All Date: 01-May-93 06:51:59 Having downloaded Tume it is indeed excellent! I noticed how the contours were used for collision detection. Anybody got any ideas on exactly how these are used for such,is it simply a certain colour used for collision detection? MC ........................................................................... Fm: Dan Corritore 70243,1110 # 346709 To: Mark Hula 100047,110 (X) Date: 02-May-93 23:03:50 I'd assume that they used a mask for the collision detection. If you remember, the collision layer was placed 'over' the tiles, so you could see it..of course, in a game, that would look quite silly! Anyway, I don't like the way they allow you to hook any collision tile to any place on the map.. I mean, I like to have the color tiles themselves holding the collision stuff, not the map.. if you would ever need to have a different sort of collision mask for the tile(which is probably quite rare), you'd just declare a new tile connected to the new mask. This would keep the size down (instead of having an extra map(for the collision indexes), you have just a few more tiles). Did you understand that? By the way, did you notice that the program was slow? I have a 386sx 16 mhz computer, and it ran pretty slowly, from what I remember. Well, anyway, after playing around with their editor for a little while, I decided to do my own.. who knows, you might decide to do the same!<g> _Dan ........................................................................... Fm: Mark Hula 100047,110 # 346838 To: Dan Corritore 70243,1110 (X) Date: 03-May-93 04:26:23 Hi, Not sure I understand you on how the collisions work within tUME. It ran fast enough on my machine...50Mhz 486! <g> MC ........................................................................... Fm: Randy @ Safari 71165,3600 # 346914 To: Dan Corritore 70243,1110 (X) Date: 03-May-93 09:55:34 Actually, the TUME method of collission detection is quite advanced. I prefer it because the mask only takes up 128 bytes as opposed to 256+128 for a 16x16 tile + mask. Besides, it only takes two machine instructions to find and read the mask. Randy ........................................................................... Fm: Dan Corritore 70243,1110 # 346983 To: Randy @ Safari 71165,3600 (X) Date: 03-May-93 13:32:07 <<Actually, the TUME method of collission detection is quite advanced. I prefer it because the mask only takes up 128 bytes as opposed to 256+128 for a 16x16 tile + mask. Besides, it only takes two machine instructions to find and read the mask.>> I don't understand.. I thought they had as many collision masks as they did tile indexes in the map. If so, then adding the mask data would double the size of the world map! There is no benefit to that, let me tell you! Instead, using what I mentioned (connecting the mask to the tile, and creating a new tile for each new mask-- a very rare thing to do, yes), you'd use up _way_ less space, especially for large worlds. And besides, it takes only 2 instructions to find and read the mask also! ;) _Dan ........................................................................... Fm: Randy @ Safari 71165,3600 # 347096 To: Dan Corritore 70243,1110 Date: 03-May-93 16:37:33 not true. You do not have as masked attribute for every tile. If you did, you'd be stupid. Some tiles have hard attributes while only those requiring special circumstances have masked attribs. In this case, making a seperate tile for each instance would be a waste of space. Randy ........................................................................... Fm: Mark Hula 100047,110 # 345452 To: All Date: 01-May-93 09:46:30 Hi All!, Back to my squares again (after the mess I made with my last message!). If I have *** *** *** by finding the first (top left) one then moving in an ever smaller concentric square I can find out if its whole or not (solid),but I can't work out the code!-as usual this message is as clear as mud!! MC 'Talking Trash' P.S Randy!,what collision technique did you use in Storm? ........................................................................... Fm: Bob Provencher/GD SL 71621,2632 # 373881 To: Randy @ Safari 71165,3600 Date: 11-Jun-93 19:31:30 Hi Randy - Almost forgot about you and the collision detection. Let's see, I've done it, but it's not very fast, I'll leave it to you guys to optimize it, I'll just write some c++ code to give you the general idea. first the prototypes for the functions used but not shown class sprite { bitmap image; bitmap mask; bitmap& mask() { return mask; } } int rect::intersect( rect, rect ); void bitmap::resize( rect ); void bitmap::blit( bitmap&, rect&, int = COPY ); void bitmap::getpixel( int, int ); int sprite::intersect( sprite& s ) { rect int_rect; bitmap work; color white( 15 ); if ( boundingbox().intersect( sprite2.boundingbox(), int_rect ) ) { work.resize( intrect ); mask().blit( work, intrect ); sprite2.mask().blit( work, intrect, XOR ); for ( int y = 0; y < intrect.height(); y++ ) for ( int x = 0; x < intrect.width(); x++ ) if ( work.getpixel( x, y ) == white ) return TRUE; return FALSE; } else return FALSE; } ...........................................................................